/*
https://leetcode-cn.com/problems/repeated-string-match/solution/zhong-fu-die-jia-zi-fu-chuan-pi-pei-by-l-vnye/
 */
public class Solution686 {
    public int repeatedStringMatch(String a, String b) {
        int m=a.length(),n=b.length();
        int index=str(a,b);
        if (index==-1){
            return -1;
        }else if (m-index>=n){
            return 1;
        }else {
            return (n+index-m-1)/m+2;
        }
    }

    int str(String a,String b){
        int m=a.length(),n=b.length();
        if (n==0){
            return 0;
        }
        int[] pi=new int[n];
        for (int i=1,j=0;i<n;i++){
            while (j>0 && b.charAt(i)!=b.charAt(j)){
                j=pi[j-1];
            }
            if (b.charAt(i)==b.charAt(j)){
                j++;
            }
            pi[i]=j;
        }
        for (int i=0,j=0;i-j<m;i++){
            while (j>0 && a.charAt(i%m)!=b.charAt(j)){
                j=pi[j-1];
            }
            if (a.charAt(i%m)==b.charAt(j)){
                j++;
            }
            if (j==n){
                return i-n+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution686().repeatedStringMatch("abcd","cdabcdab"));
    }
}
